package sort;

/**
 * Created with IntelliJ IDEA.
 * Description: 七大排序算法
 * User: Li_yizYa
 * Date: 2025/9/10
 * Time: 15:00
 */
public class Sort {
    public static void main(String[] args) {
        int[] nums = {6,5,4,4,3,1,2,10,8};
        mergeSort(nums, 0, nums.length - 1);
//        mergeSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    /**
     * 归并排序
     * @param nums
     * @param left
     * @param right
     */
    private static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }
    private static void merge(int[] nums, int left, int right, int mid) {
        int[] tmp = new int[right - left + 1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int index = 0;
        while (s1 <= e1 && s2 <= e2) {
            if (nums[s1] > nums[s2]) { // 确保是稳定的排序算法
                tmp[index++] = nums[s2++];
            } else {
                tmp[index++] = nums[s1++];
            }
        }
        while (s1 <= e1) {
            tmp[index++] = nums[s1++];
        }
        while (s2 <= e2) {
            tmp[index++] = nums[s2++];
        }
        for (int i = 0; i < index; i++) {
            nums[i + left] = tmp[i];
        }
    }
    /**
     *  快速排序
     * @param nums
     */
    private static void quickSort(int[] nums, int left, int right) {
        if (nums == null || left > right) {
            return;
        }
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }
    private static int partition(int[] nums, int left, int right) {
        int tmp = nums[left];
        while (left < right) {
            // 从右边找第一个比tmp小的元素
            while (left < right && nums[right] >= tmp) {
                right--;
            }
            nums[left] = nums[right];
            // 从左边找第一个大于 tmp 的元素
            while (left < right && nums[left] <= tmp) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = tmp;
        return left;
    }

    /**
     * 冒泡排序
     * @param nums
     */
    private static void bubbleSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int flag = 0;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j + 1] < nums[j]) {
                    int tmp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = tmp;
                    flag = 1;
                }
            }
            if (flag == 0) {
                break;
            }
        }
    }

    /**
     * 选择排序
     * @param nums
     */
    private static void selectSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            int min = nums[minIndex];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    minIndex = j;
                }
            }
            nums[minIndex] = nums[i];
            nums[i] = min;
        }
    }
    /**
     * 希尔排序
     * @param nums
     */
    private static void shellSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int gap = nums.length / 2;
        while (gap > 0) {
            shell(nums, gap);
            gap /= 2;
        }
    }
    // 6  5  4  4  3  1  2  10  8
    //
    private static void shell(int[] nums, int gap) {
        for (int i = gap; i < nums.length; i++) {
            int j = i - gap;
            int tmp = nums[i];
            for (; j >= 0; j -= gap) {
                if (nums[j] > tmp) {
                    nums[j + gap] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + gap] = tmp;
        }
    }
    /**
     * 直接插入排序
     * @param nums
     */
    private static void insertSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        for (int i = 1; i < nums.length; i++) { // 待排序列
            int j = i - 1;
            int tmp = nums[i];
            for (; j >= 0; j--) {
                if (nums[j] > tmp) {
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = tmp;
        }
    }

}
